package com.yanceysong.codetop.s11_s20;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;


public class S15_Mid_46_全排列 {
    /**
     * S15_Mid_46_全排列
     * <p>
     * <a href="https://leetcode.cn/problems/permutations/">...</a>
     * <p>
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     * <p>
     * 示例 2：
     * 输入：nums = [0,1]
     * 输出：[[0,1],[1,0]]
     * <p>
     * 示例 3：
     * 输入：nums = [1]
     * 输出：[[1]]
     * <p>
     * 解题思路：回溯算法（Backtracking）
     * 1. 全排列问题是经典的回溯算法应用场景
     * 2. 我们使用交换的方式来生成排列，避免使用额外的 visited 数组
     * 3. 对于每个位置，我们尝试放入所有可能的数字
     * 4. 当填满所有位置时，将当前排列加入结果集
     * 5. 回溯时撤销之前的选择
     * <p>
     * 图解算法（以 [1,2,3] 为例）：
     * <p>
     * 初始状态: [1,2,3]  first=0
     * .         ↑
     * <p>
     * 第一层递归：
     * i=0: swap(0,0) → [1,2,3]  递归 first=1
     * i=1: swap(0,1) → [2,1,3]  递归 first=1
     * i=2: swap(0,2) → [3,2,1]  递归 first=1
     * <p>
     * 以 [1,2,3] first=1 为例的第二层：
     * i=1: swap(1,1) → [1,2,3]  递归 first=2
     * i=2: swap(1,2) → [1,3,2]  递归 first=2
     * <p>
     * 第三层 first=2：
     * i=2: swap(2,2) → [1,2,3]  first=3 → 添加到结果
     * <p>
     * 回溯过程：
     * 1. 交换元素进入下一层
     * 2. 递归返回后，再次交换恢复原状态
     * 3. 尝试下一个可能的交换
     * <p>
     * 时间复杂度：O(n! * n) - n! 个排列，每个排列需要 O(n) 时间复制
     * 空间复杂度：O(n) - 递归栈深度
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums.length
                , Arrays.stream(nums).boxed().collect(Collectors.toCollection(ArrayList::new))
                , res,
                0);
        return res;
    }

    /**
     * 回溯函数
     *
     * @param numArrayLength 数组长度
     * @param numArray       当前排列
     * @param result         结果集
     * @param startIndex     当前要填充的位置
     */
    public void backtrack(int numArrayLength, List<Integer> numArray, List<List<Integer>> result, int startIndex) {
        // 所有数都填完了，添加到结果集
        // 说明已经确定到了最后一位数字，可以认为排列结束，收集
        if (startIndex == numArrayLength) {
            result.add(new ArrayList<>(numArray));
        }
        for (int i = startIndex; i < numArrayLength; i++) {
            // 动态维护数组：将第i个元素交换到startIndex位置
            // 即 确定第i个位置的数字，剩下的i+n位置去递归完成
            java.util.Collections.swap(numArray, startIndex, i);
            // 继续递归填下一个数
            backtrack(numArrayLength, numArray, result, startIndex + 1);
            // 撤销操作：恢复原来的顺序
            java.util.Collections.swap(numArray, startIndex, i);
        }
    }

    public static void main(String[] args) {
        S15_Mid_46_全排列 solution = new S15_Mid_46_全排列();

        // 测试用例1：[1,2,3]
        System.out.println("=== 测试用例1：[1,2,3] ===");
        int[] nums1 = {1, 2, 3};
        List<List<Integer>> result1 = solution.permute(nums1);
        System.out.println("输入：[1,2,3]");
        System.out.println("输出：" + result1);
        System.out.println("排列数量：" + result1.size());
        System.out.println();

        // 测试用例2：[0,1]
        System.out.println("=== 测试用例2：[0,1] ===");
        int[] nums2 = {0, 1};
        List<List<Integer>> result2 = solution.permute(nums2);
        System.out.println("输入：[0,1]");
        System.out.println("输出：" + result2);
        System.out.println("排列数量：" + result2.size());
        System.out.println();

        // 测试用例3：[1]
        System.out.println("=== 测试用例3：[1] ===");
        int[] nums3 = {1};
        List<List<Integer>> result3 = solution.permute(nums3);
        System.out.println("输入：[1]");
        System.out.println("输出：" + result3);
        System.out.println("排列数量：" + result3.size());
        System.out.println();

        // 测试用例4：[1,2,3,4] - 更复杂的例子
        System.out.println("=== 测试用例4：[1,2,3,4] ===");
        int[] nums4 = {1, 2, 3, 4};
        List<List<Integer>> result4 = solution.permute(nums4);
        System.out.println("输入：[1,2,3,4]");
        System.out.println("排列数量：" + result4.size() + " (应该是 4! = 24)");
        System.out.println("前5个排列：");
        for (int i = 0; i < Math.min(5, result4.size()); i++) {
            System.out.println("  " + result4.get(i));
        }
    }
}

